package com.uhu.code;

import java.util.HashMap;
import java.util.Map;

/**
 * 76.最小覆盖子串
 * https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution76 {
    public String minWindow(String s, String t) {
        int tSize = t.length();
        int sSize = s.length();
        if (tSize > sSize) {
            return "";
        }

        Map<Character, Integer> map = new HashMap<>(52);
        Map<Character, Integer> windows = new HashMap<>();
        for (int i = 0; i < tSize; i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }
        int validChar = 0;
        int start = 0, end = 0;
        int right = 0, left = 0;
        Boolean hasValue = false;
        while (right < sSize) {
            char temp = s.charAt(right);
            right++;
            if (map.containsKey(temp)) {
                windows.put(temp, windows.getOrDefault(temp, 0) + 1);
                if (map.get(temp).equals(windows.get(temp))) {
                    // 有效字符+1
                    validChar++;
                }
            }
            while (left <= right && validChar == map.size()) {
                if ((start == 0 && end == 0) || (right - left < end - start)) {
                    // 记录最小的区间
                    start = left;
                    end = right;
                }
                // 字符有效？
                char l = s.charAt(left);
                left++;
                if (map.containsKey(l) && windows.containsKey(l)) {
                    if (map.get(l).equals(windows.get(l))) {
                        // 有效字符-1
                        validChar--;
                        hasValue = true;
                    }
                    windows.put(l, windows.getOrDefault(l, 0) - 1);
                }
            }
        }
        if (hasValue) {
            return s.substring(start, end);
        } else {
            return "";
        }
    }
}
